/*
** Implementation of Threaded AVL tree.
*/

#include "tavl.h"

void *key_of_item(void *dataP);
void *create_item(void *dataP);
void *duplicate_item(void *dest_p, void *src_p);
void destroy_item(void *dataP);
void *mem_alloc(size_t size);
void mem_free(void *ptr);

static TAVL_nodeptr remove_node(TAVL_treeptr tree, TAVL_nodeptr p, char *deltaht);
static TAVL_nodeptr remove_max(TAVL_nodeptr p, TAVL_nodeptr * maxnode, char *deltaht);
static TAVL_nodeptr remove_min(TAVL_nodeptr p, TAVL_nodeptr * minnode, char *deltaht);

#ifdef TAVL_DEBUG
#define assert(condM) ((!(condM)) ? capwap_dbg("assert failed") : 0)
#else /* TAVL_DEBUG */
#define assert(condM) ((void)0)
#endif /* TAVL_DEBUG */

#define UnUseArg(arg)

/**************************************************************************
** TAVL library private definitions.
**************************************************************************/
/* Private: for internal use by tavl*.c library routines only! */

/*   See note below
     ... recommended that TAVL_USE_BIT_FIELDS remain commented out,
     ... both for efficiency (speed) and universiality.
#define TAVL_USE_BIT_FIELDS
*/

typedef struct tavlnode {
	void *dataptr;
	struct tavlnode *Lptr, *Rptr;
#if !defined TAVL_USE_BIT_FIELDS
	/* see NOTE below */
	signed char bf;		/* assumes values -2..+2 */
	char Lbit;		/* 0 or 1 */
	char Rbit;		/* 0 or 1 */
#else
	signed int bf:3;	/* assumes values -2..+2 */
	unsigned int Lbit:1;
	unsigned int Rbit:1;
#endif
} TAVL_NODE;

typedef struct tavltree {
	TAVL_nodeptr head;
	int (*cmp) (void *, void *, void *);
	void *(*key_of) (void *);
	void *(*make_item) (void *);
	void (*free_item) (void *);
	void *(*copy_item) (void *, void *);
	void *(*alloc) (size_t);
	void (*dealloc) (void *);
	int tavl_count;
	void *paramP;
} TAVL_TREE;

/* end private */

#define RIGHT   -1
#define LEFT    +1
#define THREAD  0
#define LINK    1
#define LLINK(x)    ((x)->Lbit)
#define RLINK(x)    ((x)->Rbit)
#define LTHREAD(x)  (!LLINK(x))
#define RTHREAD(x)  (!RLINK(x))
#define Leftchild(x)    (LLINK(x) ? (x)->Lptr : NULL)
#define Rightchild(x)   (RLINK(x) ? (x)->Rptr : NULL)
#define Is_Head(x)      ((x)->Rptr == (x))
							/* always true for head node of initialized */
							/* tavl_tree, and false for all other nodes */

#define RECUR_STACK_SIZE 40	/* this is extremely enormous */

TAVL_nodeptr rebalance_tavl(TAVL_nodeptr a, char *deltaht);
/*  Returns pointer to root of rebalanced tree "a".  If rebalance reduces
    the height of tree "a", *deltaht = 1, otherwise *deltaht = 0.
    "rebalance_tavl" is called ONLY by "tavl_insert" and "tavl_delete".
    *deltaht is always 1 when "rebalance_tavl" is called by "tavl_insert";
    however, *deltaht may return 1 or 0 when called by "tavl_delete".
*/

/* Key(Id) of item. */
void *key_of_item(void *dataP)
{

	return (dataP);

}

/* Create item. */
void *create_item(void *dataP)
{

	/* Just return data pointer. */
	return (dataP);

}

/* destroy Item. */
void destroy_item(void *dataP)
{

	/* Free memory. */
	mem_free(dataP);

}

/* duplicate Item. not used now. */
void *duplicate_item(void *dest_p, void *src_p)
{

	return (src_p);

}

/* memory allocator function. */
void *mem_alloc(size_t size)
{
	return malloc(size);
}

/* memory free function. */
void mem_free(void *ptr)
{

	if (ptr != NULL) {
		free(ptr);
	}
}

/**************************************************************************
** TAVL library wrapper functions.
**************************************************************************/
int tavl_counter(TAVL_treeptr tree)
{
	return (tree->tavl_count);
}

void *tavl_node_data(TAVL_nodeptr p)
{
	return (p->dataptr);
}

TAVL_treeptr tavl_init(		/* user supplied functions: */
			      int (*compare) (void *, void *, void *),	/* compares identifiers */
			      void *(*key_of) (void *),	/* returns item identifier */
			      void *(*make_item) (void *),	/* create copy of item */
			      void (*free_item) (void *),	/* frees node's data */
			      void *(*copy_item) (void *, void *), void *(*alloc) (size_t), void (*dealloc) (void *),
			      void *paramP)
{
	TAVL_treeptr tree = NULL;

	alloc = (alloc == NULL) ? mem_alloc : alloc;
	dealloc = (dealloc == NULL) ? mem_free : dealloc;

	tree = (*alloc) (sizeof(TAVL_TREE));

	if (tree) {
		if ((tree->head = (*alloc) (sizeof(TAVL_NODE))) != NULL) {
			tree->cmp = compare;
			tree->key_of = (key_of == NULL) ? key_of_item : key_of;
			tree->make_item = (make_item == NULL) ? create_item : make_item;
			tree->free_item = (free_item == NULL) ? destroy_item : free_item;
			tree->copy_item = (copy_item == NULL) ? duplicate_item : copy_item;
			tree->alloc = alloc;
			tree->dealloc = dealloc;
			tree->head->bf = 0;
			tree->head->Lbit = THREAD;
			tree->head->Rbit = LINK;
			tree->head->dataptr = NULL;
			tree->head->Lptr = tree->head;
			tree->head->Rptr = tree->head;
			tree->paramP = paramP;
			tree->tavl_count = 0;
		} else {
			(*dealloc) (tree);
			tree = NULL;
		}
	}
	return tree;
}

void tavl_destroy(TAVL_treeptr tree)
{
	register TAVL_nodeptr q;
	register TAVL_nodeptr p = tavl_succ(tavl_reset(tree));

	while (p) {
		p = tavl_succ(q = p);
		(*tree->free_item) (q->dataptr);
		(*tree->dealloc) (q);
	}
	(*tree->dealloc) (tree->head);
	(*tree->dealloc) (tree);
}

TAVL_nodeptr tavl_insert(TAVL_treeptr tree, void *item, int replace)
				/*
				   Using the user supplied (key_of) & (cmp) functions, *tree
				   is searched for a node which matches *item. If a match is
				   found, the new item replaces the old if & only if
				   replace != 0.  If no match is found the item is inserted
				   into *tree.  "tavl_insert" returns a pointer to the node
				   inserted into or found in *tree. "tavl_insert" returns
				   NULL if & only if it is unable to allocate memory for
				   a new node.
				 */
{
	TAVL_nodeptr a, y, f;
	register TAVL_nodeptr p, q;
	register int cmpval = -1;	/* cmpval must be initialized - if tree is */
	int side;		/* empty node inserted as LeftChild of head */
	char junk;

	/*  Locate insertion point for item.  "a" keeps track of most
	   recently seen node with (bf != 0) - or it is the top of the
	   tree, if no nodes with (p->bf != 0) are encountered.  "f"
	   is parent of "a".  "q" follows "p" through tree.
	 */

	q = tree->head;
	a = q;
	f = NULL;
	p = Leftchild(q);

	while (p) {
		if (p->bf) {
			a = p;
			f = q;
		}

		q = p;

		cmpval = (*tree->cmp) ((*tree->key_of) (item), (*tree->key_of) (p->dataptr), tree->paramP);
		if (cmpval < 0)
			p = Leftchild(p);
		else if (cmpval > 0)
			p = Rightchild(p);
		else {
			if (replace) {
				void *temp = (*tree->make_item) (item);
				if (temp) {
					(*tree->free_item) (p->dataptr);
					p->dataptr = temp;
				} else
					p = NULL;
			}
			return p;
		}
	}

	/* wasn't found - create new node as child of q */

	y = (*tree->alloc) (sizeof(TAVL_NODE));

	if (y) {
		y->bf = 0;
		y->Lbit = THREAD;
		y->Rbit = THREAD;
		if ((y->dataptr = (*tree->make_item) (item)) == NULL) {
			(*tree->dealloc) (y);
			return NULL;	/* must be out of memory */
		}
	} else
		return NULL;	/* out of memory */

	if (cmpval < 0) {	/* connect to tree and thread it */
		y->Lptr = q->Lptr;
		y->Rptr = q;
		q->Lbit = LINK;
		q->Lptr = y;
	} else {
		y->Rptr = q->Rptr;
		y->Lptr = q;
		q->Rbit = LINK;
		q->Rptr = y;
	}

	/*  Adjust balance factors on path from a to q.  By definition of "a",
	   all nodes on this path have bf = 0, and so will change to LEFT or
	   RIGHT.
	 */
	/* Increase nodes count. */
	tree->tavl_count++;

	if ((a == tree->head)
	    || ((*tree->cmp) ((*tree->key_of) (item), (*tree->key_of) (a->dataptr), tree->paramP) < 0)) {
		p = a->Lptr;
		side = LEFT;
	} else {
		p = a->Rptr;
		side = RIGHT;
	}

	/* adjust balance factors */

	while (p != y) {
		if ((*tree->cmp) ((*tree->key_of) (p->dataptr), (*tree->key_of) (item), tree->paramP) > 0) {
			p->bf = LEFT;
			p = p->Lptr;
		} else {
			p->bf = RIGHT;
			p = p->Rptr;
		}
	}

	tree->head->bf = 0;	/* if a==tree->head, tree is already balanced */

	/* Is tree balanced? */

	if (abs(a->bf += side) < 2)
		return y;

	p = rebalance_tavl(a, &junk);

	assert(junk);		/* rebalance always sets junk to 0 */

	assert(f);		/* f was set non-NULL by the search loop */

	if (f->Rptr != a)
		f->Lptr = p;
	else
		f->Rptr = p;

	return y;
}

/*  Development note:  the routines "remove_min" and "remove_max" are
    true recursive routines; i.e., they make calls to themselves. The
    routine "tavl_delete" simulates recursion using a stack (a very deep
    one that should handle any imaginable tree size - up to approximately
    1 million squared nodes).  I arrived at this particular mix by using
    Borland's Turbo Profiler and a list of 60K words as a test file to
    example1.c, which should be included in the distribution package.
    -BCH
*/

void *tavl_delete(TAVL_treeptr tree, void *key)
{
	char rb, deltaht;
	int side;
	int found = deltaht = 0;
	register TAVL_nodeptr p = Leftchild(tree->head);
	register int cmpval = -1;
	register TAVL_nodeptr q = NULL;
	void *dataP;

	struct stk_item {
		int side;
		TAVL_nodeptr p;
	} block[RECUR_STACK_SIZE];

	struct stk_item *next = block;	/* initialize recursion stack */

#define PUSH_PATH(x,y)  (next->p = (x),  (next++)->side = (y))
#define POP_PATH(x)     (x = (--next)->side, (next->p))

	tree->head->bf = 0;	/* prevent tree->head from being rebalanced */

	PUSH_PATH(tree->head, LEFT);

	while (p) {
		cmpval = (*tree->cmp) (key, (*tree->key_of) (p->dataptr), tree->paramP);
		if (cmpval > 0) {
			PUSH_PATH(p, RIGHT);
			p = Rightchild(p);
		} else if (cmpval < 0) {
			PUSH_PATH(p, LEFT);
			p = Leftchild(p);
		} else {	/* cmpval == 0 */

			q = p;
			p = NULL;
			found = 1;
		}
	}			/* end while(p) */

	if (!found)
		return NULL;

	/* decrease nodes count */
	tree->tavl_count--;
	dataP = q->dataptr;

	q = remove_node(tree, q, &deltaht);

	do {
		p = POP_PATH(side);

		if (side != RIGHT)
			p->Lptr = q;
		else
			p->Rptr = q;

		q = p;
		rb = 0;

		if (deltaht) {
			p->bf -= side;
			switch (p->bf) {
			case 0:
				break;	/* longest side shrank to equal shortest */
				/* therefor deltaht remains true */
			case LEFT:
			case RIGHT:
				deltaht = 0;	/* other side is deeper */
				break;

			default:{
					q = rebalance_tavl(p, &deltaht);
					rb = 1;
				}
			}
		}
	} while ((p != tree->head) && (rb || deltaht));

	return dataP;

#undef PUSH_PATH
#undef POP_PATH

}				/* tavl_delete */

TAVL_nodeptr tavl_find(TAVL_treeptr tree, void *key)
				/* Return pointer to tree node containing data-item
				   identified by "key"; returns NULL if not found */
{
	register TAVL_nodeptr p = Leftchild(tree->head);
	register int side;
	while (p) {
		side = (*tree->cmp) (key, (*tree->key_of) (p->dataptr), tree->paramP);
		if (side > 0)
			p = Rightchild(p);
		else if (side < 0)
			p = Leftchild(p);
		else
			return p;
	}
	return NULL;
}

TAVL_nodeptr tavl_reset(TAVL_treeptr tree)
{
	return tree->head;
}

TAVL_nodeptr tavl_succ(TAVL_nodeptr p)
{
	register TAVL_nodeptr q;

	if (!p)
		return NULL;

	q = p->Rptr;

	if (RLINK(p))
		while (LLINK(q))
			q = q->Lptr;

	return (Is_Head(q) ? NULL : q);
}

TAVL_nodeptr tavl_pred(TAVL_nodeptr p)
{
	register TAVL_nodeptr q;

	if (!p)
		return NULL;

	q = p->Lptr;

	if (LLINK(p))
		while (RLINK(q))
			q = q->Rptr;

	return (Is_Head(q) ? NULL : q);
}

TAVL_nodeptr rebalance_tavl(TAVL_nodeptr a, char *deltaht)
{
	TAVL_nodeptr b, c, sub_root = NULL;	/* sub_root will be the return value, */
	/* and the root of the newly rebalanced */
	/* sub-tree */

	/*  definition(tree-height(X)) : the maximum    */
	/*      path length from node X to a leaf node. */
	*deltaht = 0;		/*  *deltaht is set to 1 if and only if         */
	/*      tree-height(rebalance()) < tree-height(a) */

	if (Is_Head(a)		/* Never rebalance the head node! */
	    ||abs(a->bf) <= 1)	/* tree "a" is balanced - nothing more to do */
		return (a);

	if (a->bf == LEFT + LEFT) {
		b = a->Lptr;
		if (b->bf != RIGHT) {	/* LL rotation */
			if (RTHREAD(b)) {	/* b->Rptr is a thread to "a" */
				assert(b->Rptr == a);
				a->Lbit = THREAD;	/* change from link to thread */
				b->Rbit = LINK;	/* change thread to link */
			} else {
				a->Lptr = b->Rptr;
				b->Rptr = a;
			}

			*deltaht = b->bf ? 1 : 0;
			a->bf = -(b->bf += RIGHT);

			sub_root = b;
		} else {	/* LR rotation */
			*deltaht = 1;

			c = b->Rptr;
			if (LTHREAD(c)) {
				assert(c->Lptr == b);
				c->Lbit = LINK;
				b->Rbit = THREAD;
			} else {
				b->Rptr = c->Lptr;
				c->Lptr = b;
			}

			if (RTHREAD(c)) {
				assert(c->Rptr == a);
				c->Rbit = LINK;
				a->Lptr = c;
				a->Lbit = THREAD;
			} else {
				a->Lptr = c->Rptr;
				c->Rptr = a;
			}

			switch (c->bf) {
			case LEFT:
				b->bf = 0;
				a->bf = RIGHT;
				break;

			case RIGHT:
				b->bf = LEFT;
				a->bf = 0;
				break;

			case 0:
				b->bf = 0;
				a->bf = 0;
			}

			c->bf = 0;

			sub_root = c;
		}
	} else if (a->bf == RIGHT + RIGHT) {
		b = a->Rptr;
		if (b->bf != LEFT) {	/* RR rotation */
			if (LTHREAD(b)) {	/* b->Lptr is a thread to "a" */
				assert(b->Lptr == a);
				a->Rbit = THREAD;	/* change from link to thread */
				b->Lbit = LINK;	/* change thread to link */
			} else {
				a->Rptr = b->Lptr;
				b->Lptr = a;
			}
			*deltaht = b->bf ? 1 : 0;
			a->bf = -(b->bf += LEFT);

			sub_root = b;
		} else {	/* RL rotation */
			*deltaht = 1;

			c = b->Lptr;
			if (RTHREAD(c)) {
				assert(c->Rptr == b);
				c->Rbit = LINK;
				b->Lbit = THREAD;
			} else {
				b->Lptr = c->Rptr;
				c->Rptr = b;
			}

			if (LTHREAD(c)) {
				assert(c->Lptr == a);
				c->Lbit = LINK;
				a->Rptr = c;
				a->Rbit = THREAD;
			} else {
				a->Rptr = c->Lptr;
				c->Lptr = a;
			}

			switch (c->bf) {
			case RIGHT:
				b->bf = 0;
				a->bf = LEFT;
				break;

			case LEFT:
				b->bf = RIGHT;
				a->bf = 0;
				break;

			case 0:
				b->bf = 0;
				a->bf = 0;
			}

			c->bf = 0;

			sub_root = c;
		}
	}

	return sub_root;

}				/* end rebalance */

static TAVL_nodeptr remove_node(TAVL_treeptr tree, TAVL_nodeptr p, char *deltaht)
{
	char dh;
	TAVL_nodeptr q;

	*deltaht = 0;

	if (p->bf != LEFT) {
		if (RLINK(p)) {
			p->Rptr = remove_min(p->Rptr, &q, &dh);
			if (dh) {
				p->bf += LEFT;	/* becomes 0 or LEFT */
				*deltaht = (p->bf) ? 0 : 1;
			}
		} else {	/* leftchild(p),rightchild(p) == NULL */
			assert(p->bf == 0);
			assert(LTHREAD(p));

			*deltaht = 1;	/* p will be removed, so height changes */
			if (p->Rptr->Lptr == p) {	/* p is leftchild of it's parent */
				p->Rptr->Lbit = THREAD;
				q = p->Lptr;
			} else {	/* p is rightchild of it's parent */
				assert(p->Lptr->Rptr == p);
				p->Lptr->Rbit = THREAD;
				q = p->Rptr;
			}
			(*tree->dealloc) (p);
			return q;
		}
	} else {		/* p->bf == LEFT */
		p->Lptr = remove_max((p->Lptr), &q, &dh);
		if (dh) {
			p->bf += RIGHT;	/* becomes 0 or RIGHT */
			*deltaht = (p->bf) ? 0 : 1;
		}
	}

	p->dataptr = q->dataptr;
	(*tree->dealloc) (q);
	return p;
}

static TAVL_nodeptr remove_min(TAVL_nodeptr p, TAVL_nodeptr * minnode, char *deltaht)
{
	char dh = *deltaht = 0;

	if (LLINK(p)) {		/* p is not minimum node */
		p->Lptr = remove_min(p->Lptr, minnode, &dh);
		if (dh) {
			p->bf += RIGHT;
			switch (p->bf) {
			case 0:
				*deltaht = 1;
				break;
			case RIGHT + RIGHT:
				p = rebalance_tavl(p, deltaht);
			}
		}
		return p;
	} else {		/* p is minimum */
		*minnode = p;
		*deltaht = 1;
		if (RLINK(p)) {
			assert(p->Rptr->Lptr == p);
			assert(LTHREAD(p->Rptr) && RTHREAD(p->Rptr));

			p->Rptr->Lptr = p->Lptr;
			return p->Rptr;
		} else if (p->Rptr->Lptr != p) {	/* was first call to remove_min, */
			p->Lptr->Rbit = THREAD;	/* from "remove", not remove_min */
			return p->Rptr;	/* p is never rightchild of head */
		} else {
			p->Rptr->Lbit = THREAD;
			return p->Lptr;
		}
	}
}

static TAVL_nodeptr remove_max(TAVL_nodeptr p, TAVL_nodeptr * maxnode, char *deltaht)
{
	char dh = *deltaht = 0;

	if (RLINK(p)) {		/* p is not maximum node */
		p->Rptr = remove_max(p->Rptr, maxnode, &dh);
		if (dh) {
			p->bf += LEFT;
			switch (p->bf) {
			case 0:
				*deltaht = 1;
				break;
			case LEFT + LEFT:
				p = rebalance_tavl(p, deltaht);
			}
		}
		return p;
	} else {		/* p is maximum */
		*maxnode = p;
		*deltaht = 1;
		if (LLINK(p)) {
			assert(LTHREAD(p->Lptr) && RTHREAD(p->Lptr));
			assert(p->Lptr->Rptr == p);

			p->Lptr->Rptr = p->Rptr;
			return p->Lptr;
		} else if (p->Rptr->Lptr == p) {	/* p is leftchild of its parent */
			p->Rptr->Lbit = THREAD;	/* test must use p->Rptr->Lptr */
			return p->Lptr;	/* because p may be predecessor */
		} /* of head node */
		else {
			p->Lptr->Rbit = THREAD;	/* p is rightchild of its parent */
			return p->Rptr;
		}
	}
}
